package summary;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/is-subsequence/
 */
public class Title392 {

    /**
     * dp[i][j]表示以下标为i-1的A和以下标为j-1的B，最长公共子序列
     *
     * @param s
     * @param t
     * @return
     */
    public static boolean isSubsequence(String s, String t) {
        if ("".equals(s)) {
            return true;
        }
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        int max = 0;
        for (int i = 1; i <= s.length(); i++) {
            int temp = max;
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    //此时不相等 0 - i-1  0 - j-1
                    dp[i][j] = dp[i][j - 1];
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                }
                if (dp[i][j] == s.length()) {
                    return true;
                }
            }
            if (max == temp) {
                return false;
            }
        }
        return false;
    }


    public boolean isSubsequence1(String s, String t) {
        if (s.equals(t)) {
            return true;
        }
        int i = 0;
        for (int j = 0; j < t.length(); j++) {
            if (i < s.length() && s.charAt(i) == t.charAt(j)) {
                i++;
            }
            if (i >= s.length()) {
                return true;
            }
        }
        return false;
    }



    public boolean isSubsequence2(String s, String t) {
        if ("".equals(s)) {
            return true;
        }
        int n = s.length();
        int m = t.length();
        //dp[i][j]表示 s下标为i-1, t下标为j-1时，最长公共子序列子序列
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            int flag = 0;
            int temp = 0;
            for (int j = 1; j <= m; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = dp[i][j - 1];
                }
                if (dp[i][j] == s.length()) {
                    return true;
                }
                if (dp[i][j] > flag) {
                    flag = dp[i][j];
                }
            }
            if (temp == flag) {
                return false;
            }
        }
        return false;
    }





    public static void main(String[] args) {
        String s = "abc";
        String t = "ahbgdc";
        boolean subsequence = isSubsequence(s, t);
        System.out.println(subsequence);
    }
}
